#include <stdio.h>
#include <stdlib.h>

void quick_sort(int *_array, int _len); /* 快速排序函数 */
static void quick_sortf(int *_array, int _low, int _high); /* 快速排序辅助函数 */

void print_array(const int *_array, int _len); /* 打印数组 */


int main(int argc, const char* argv)
{
    int len,*array, i;
    printf("请输入数组的大小:\n");
    scanf("%d", &len);
    if (len <= 0) return -1;
    
    array = (int*)malloc(sizeof(int) * len);
    if (array == NULL) return -1;
    
    printf("请输入数据:\n");
    for (i = 0; i < len; ++i) scanf("%d", &array[i]);
    
    printf("原数组:\n");
    print_array(array, len);
    quick_sort(array, len);
    printf("快速排序后的数组:\n");
    print_array(array, len);


    return 0;
}

static void quick_sortf(int *_array, int _low, int _high)
{
    if (_low >= _high) return;

    int i = _low, j = _high, base = _array[_low], temp;
    while (i != j)
    {
        while (_array[j] >= base && i < j) j--;
        while (_array[i] <= base && i < j) i++;
        
        temp = _array[i];
        _array[i] = _array[j];
        _array[j] = temp;
    }
    _array[_low] = _array[i];
    _array[i] = base;

    quick_sortf(_array, _low, i - 1);
    quick_sortf(_array, i + 1, _high);
}

void quick_sort(int *_array, int _len)
{
    quick_sortf(_array, 0, _len - 1);
}

void print_array(const int *_array, int _len)
{
    int i = 0;
    printf("[ ");
    for (; i < _len; ++i) printf("%d ", _array[i]);
    printf("]\n");
}